題目連結: Isomorphic Strings

題目描述為給定兩字串 s,t 要判斷這兩個字串是否為同構。
此題同構的意思是指 s,t 中的全部字元可以被全部互相取代。
題目還有補充說明可假設此題 s,t 長度一樣。

例子 1 : s="egg", t="add" output=true。
例子 2 : s="foo", t="bar" output=false。
例子 3 : s="paper", t="title" output=true。

思路 1 : Hash 法

我們可以建立兩個陣列,將 s,t 中每個字元分別對應到一個非0的數值，當該字元是第一次出現時賦值，第二次出現時檢查兩個陣列中字元是否對應到同一個數值，若不是則返回 false。

• 複雜度評估
  當字串長度為 N 時，我們至多需要遍歷整個陣列一次，時間複雜度為 O(N)。
  此方法建立了兩個陣列來儲存每個字元對應的數值，字元的ASCII碼數值範圍介於 [1,128]，與 N 大小無關，空間複雜度為 O(1)。

參考程式碼

func isIsomorphic(s string, t string) bool {
    
   var arrs,arrt [128]int   
   var bs,bt byte
    
	for i := 0; i < len(s); i++ {
		bs, bt = s[i], t[i]
		if arrs[bs] != arrt[bt] {
			return false
		}
		arrs[bs],arrt[bt]= i+1,i+1
	}
    
	return true
    
}

小結:

同構的數學概念為兩者本質一樣，在此題表示兩個字串有一樣的組成結構。我們也可以直接將兩字串字元的數值互相對應，我將此方法做為解法 2，加上簡單的測試，上傳程式碼到此。